package com.leetcode.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 回文串 是正着读和反着读都一样的字符串。
 * 示例 1：
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * 输入：s = "a"
 * 输出：[["a"]]
 * 提示：
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xaxi62/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Code131 {

    public static void main(String[] args) {
        String s = "aab";
        Code131 f = new Code131();
        List<List<String>> partition = f.partition3(s);
        System.out.println(partition);

    }
    char[][] falg = null;
    List<List<String>> list = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    public List<List<String>> partition3(String s) {
        falg = new char[s.length()][s.length()];
        for(int i = 0;i<s.length();i++){
            falg[i][i] = '1';
        }
        dfs(s,0);
        return list;
    }

    private void dfs(String s, int index) {
        if(index>=s.length()){
            list.add(new ArrayList<>(temp));
            return;
        }
        for(int i = index;i<s.length();i++){
            if(isPartition(s,index,i)){
                temp.add(s.substring(index,i+1));
                dfs(s,i+1);
                temp.remove(temp.size()-1);
            }
        }
    }
    public boolean isPartition(String s,int startIndex,int endIndex){
        if(falg[startIndex][endIndex] == '1'){
            return true;
        }
        while (startIndex<endIndex){
            if(s.charAt(startIndex) == s.charAt(endIndex)){
                startIndex++;
                endIndex--;
            }else {
                return false;
            }
        }
        return true;
    }

    /*
    用来保存从任意一位置至任意一位置的子串是否是回文串，类似于动态规划中保存之前的状态来减小时间复杂度
    不同之处在于这里的状态并没有发生转移，所以不算是动态规划与回溯算法的结合
    这一步是优化时间复杂度的关键
     */
    char[][] f;
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        int len = s.length();
        /*
        它是一个二维矩阵，有三种状态值：
        0表示之前还没有计算过
        1表示从下标i到j的子串是回文串
        2表示不是回文串
        我们只用到了数组的右上半部分
        当然这里也可以使用char数组，空间复杂度更低
         */
        f = new char[len][len];
        //初始化，单个字符的肯定是回文串
        for(int i = 0;i<len;i++){
            f[i][i] = 1;
        }
        List<String> list = new ArrayList<>();
        handle(res,list,s,len,0);
        return res;
    }

    public void handle(List<List<String>> res,List<String> list,String s,Integer len,Integer index){
        //递归出口
        if(index == len){
            res.add(new ArrayList<>(list));
        }
        for(int i = index;i<len;i++){
          //判断是回文串了，加入集合
         if(check(s,index,i)){
             list.add(s.substring(index,i+1));
             //递归进入下一次层搜索
             handle(res,list,s,len,i+1);
             //回溯
             list.remove(list.size()-1);
         }
        }
    }
    //判断是否是回文串
    public boolean check(String s,int index,int end){
        //记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
        if(f[index][end] == 1){
            return true;
        }else if(f[index][end] == 2){
            return false;
        }else{
            char[] arr = s.toCharArray();
            while(index < end){
                if(arr[index] != arr[end]){
                    f[index][end] = 2;
                    return false;
                }
                index++;
                end--;
            }
            f[index][end] = 1;
            return true;
        }
    }

    /**
     * 官方题解
     * 方法一：回溯 + 动态规划预处理
     * 思路与算法
     * 由于需要求出字符串 ss 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。
     * 假设我们当前搜索到字符串的第 i 个字符，且 s[0..i−1] 位置的所有字符已经被分割成若干个回文串，
     * 并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i..j] 是一个回文串。
     * 因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i..j] 是否为回文串：
     * 如果 s[i..j] 是回文串，那么就将其加入答案数组 ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i..j] 从 ans 中移除。
     * 如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/fen-ge-hui-wen-chuan-by-leetcode-solutio-6jkv/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @author ymy
     * @date 2021/9/2 15:41
     * @param null
     * @return null
     */
    boolean[][] f1;
    List<List<String>> ret1 = new ArrayList<List<String>>();
    List<String> ans1 = new ArrayList<String>();
    int n1;
    public List<List<String>> partition1(String s) {
        n1 = s.length();
        f1 = new boolean[n1][n1];
        for (int i = 0; i < n1; ++i) {
            Arrays.fill(f1[i], true);
        }
        for (int i = n1 - 1; i >= 0; --i) {
            for (int j = i + 1; j < n1; ++j) {
                f1[i][j] = (s.charAt(i) == s.charAt(j)) && f1[i + 1][j - 1];
            }
        }
        dfs1(s, 0);
        return ret1;
    }
    public void dfs1(String s, int i) {
        if (i == n1) {
            ret1.add(new ArrayList<String>(ans1));
            return;
        }
        for (int j = i; j < n1; ++j) {
            if (f1[i][j]) {
                ans1.add(s.substring(i, j + 1));
                dfs1(s, j + 1);
                ans1.remove(ans1.size() - 1);
            }
        }
    }

    /**
     * 官方题解2
     * 方法二：回溯 + 记忆化搜索
     * 思路与算法
     * 方法一中的动态规划预处理计算出了任意的 s[i..j] 是否为回文串，我们也可以将这一步改为记忆化搜索。
     * @author ymy
     * @date 2021/9/2 15:42
     * @param null
     * @return null
     */
    int[][] f2;
    List<List<String>> ret2 = new ArrayList<List<String>>();
    List<String> ans2 = new ArrayList<String>();
    int n2;
    public List<List<String>> partition2(String s) {
        n2 = s.length();
        f2 = new int[n2][n2];
        dfs2(s, 0);
        return ret2;
    }

    public void dfs2(String s, int i) {
        if (i == n2) {
            ret2.add(new ArrayList<String>(ans2));
            return;
        }
        for (int j = i; j < n2; ++j) {
            if (isPalindrome(s, i, j) == 1) {
                ans2.add(s.substring(i, j + 1));
                dfs2(s, j + 1);
                ans2.remove(ans2.size() - 1);
            }
        }
    }

    // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
    public int isPalindrome(String s, int i, int j) {
        if (f2[i][j] != 0) {
            return f2[i][j];
        }
        if (i >= j) {
            f2[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            f2[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
            f2[i][j] = -1;
        }
        return f2[i][j];
    }




}
